package puzzle_a_estrela;

import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.Iterator;

/**
 * Implementação do estado do problema NPuzzle
 */
public final class NPuzzleEstado implements Estado {

    /** Configuração do tabuleiro */
    public final int[][] pecas;
    /** O tamanho do tabuleiro(Quadrado) */
    public final int tamTabuleiro;
    /** Move o quadrado vazio para a esquerda */
    public static Acao MOVE_ESQUERDA  = new Acao("MOVE PARA ESQUERDA");
    /** Move o quadrado vazio para a direita */
    public static Acao MOVE_DIREITA = new Acao("MOVE PARA DIREITA");
    /** Move o quadrado vazio para cima */
    public static Acao MOVE_CIMA    = new Acao("MOVE PARA CIMA");
    /** Move o quadrado vazio para baixo */
    public static Acao MOVE_BAIXO  = new Acao("MOVE PARA BAIXO");
    /** Ordem em que as ações serão testadas  */
    private static Acao[] sequenciaAcoes={MOVE_ESQUERDA, MOVE_DIREITA, MOVE_CIMA, MOVE_BAIXO};
    
    /**
     * Inicializa o tabuleiro com a configuração final, de onde todas 
     * as sequencias de movimentos considerados legais vão 
     * gerar uma configuração de tabuleiro que pode ser resolvida
     */
    public NPuzzleEstado(int tamTabuleiro) {
    	this.tamTabuleiro = tamTabuleiro;
    	this.pecas = new int[tamTabuleiro][tamTabuleiro];
    	for (int i=0; i < tamTabuleiro; i++) {
    		for (int j = 0; j<tamTabuleiro; j++) {
    			this.pecas[i][j]=i*tamTabuleiro+j+1;
    		}
    	}
    	pecas[tamTabuleiro-1][tamTabuleiro-1]=0;
    }
    
    /**
     * Novo estado gerado a partir de uma configuração de tabuleiro existente (uma cópia é gerada)
     */
    public NPuzzleEstado(NPuzzleEstado estado) {
    	this.tamTabuleiro = estado.tamTabuleiro;
        this.pecas = new int[this.tamTabuleiro][this.tamTabuleiro];
        for (int i = 0;  i< this.tamTabuleiro; i++) {
            for (int j = 0; j < this.tamTabuleiro; j++) {
                this.pecas[i][j] = estado.pecas[i][j];
            }
        }
    }

    /**
     * Novo estado gerado a partir de uma configuração de tabuleiro existente (uma cópia é gerada)
     */
    public NPuzzleEstado(int[][] estado) {
    	this.tamTabuleiro = estado.length;
        this.pecas = new int[this.tamTabuleiro][this.tamTabuleiro];
        for (int i = 0; i < this.tamTabuleiro; i++) {
            for (int j = 0; j < this.tamTabuleiro; j++) {
                this.pecas[i][j]=estado[i][j];
            }
        }
    }

    /**
     * Gera um novo estado a partir da ação aplicada a outro estado
     */
    public NPuzzleEstado(NPuzzleEstado origem, Acao acao) {
        this(origem);
        fazAcao(this,acao);
    }
    
    public static void fazAcao(NPuzzleEstado origem, Acao acao) {
        int linhaVazia=0, colunaVazia=0;
        for (int i=0; i<origem.tamTabuleiro; i++) {
            for (int j=0; j<origem.tamTabuleiro; j++) {
                if (origem.pecas[i][j]==0) {
                    linhaVazia=i;
                    colunaVazia=j;
                    break;
                }
            }
        }
        // Descobre a ser ação feita, testa se ela é valida e a realiza (implica em mudança na configuração do tabuleiro)
        if (acao==MOVE_CIMA && linhaVazia!=0) { 
            // preenche o espaço vazio com uma peça
            origem.pecas[linhaVazia][colunaVazia]=origem.pecas[linhaVazia-1][colunaVazia]; 
            // novo espaço vazio
            origem.pecas[linhaVazia-1][colunaVazia]=0; 
        } else if (acao==MOVE_BAIXO && linhaVazia!=(origem.tamTabuleiro-1)) {
            // preenche o espaço vazio com uma peça
            origem.pecas[linhaVazia][colunaVazia]=origem.pecas[linhaVazia+1][colunaVazia];
            // novo espaço vazio
            origem.pecas[linhaVazia+1][colunaVazia]=0;
        } else if (acao==MOVE_ESQUERDA && colunaVazia!=0) {
            // preenche o espaço vazio com uma peça
            origem.pecas[linhaVazia][colunaVazia]=origem.pecas[linhaVazia][colunaVazia-1];
            // novo espaço vazio
            origem.pecas[linhaVazia][colunaVazia-1]=0;
        } else if (acao==MOVE_DIREITA && colunaVazia!=(origem.tamTabuleiro-1)) {
            // preenche o espaço vazio com uma peça
            origem.pecas[linhaVazia][colunaVazia]=origem.pecas[linhaVazia][colunaVazia+1];
            // novo espaço vazio
            origem.pecas[linhaVazia][colunaVazia+1]=0;
        } else {
            throw new RuntimeException("Movimento ilegal");
        }
    }
    
    /**
     * Verifica se o estado atual é final
     */
    public boolean estadoFinal() {
        for (int i=0; i<tamTabuleiro; i++) {
            for (int j=0; j<tamTabuleiro; j++) {
                if (pecas[i][j]!=i*tamTabuleiro+j+1) {
                    if (i==(tamTabuleiro-1) && j==(tamTabuleiro-1))
                        return true;
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * Gera a partir do estado atual todos os pares Acao/Estado válidos que podem ser gerados pelo mesmo 
     */
    public AcaoEstado[] sucessores() {
        ArrayList lista = new ArrayList();
        for (int a=0; a < sequenciaAcoes.length; a++) {
            try {
                Estado state=new NPuzzleEstado(this, sequenciaAcoes[a]);
                lista.add(new AcaoEstado(sequenciaAcoes[a], state));
            } catch (RuntimeException e) {
                ; //Movimento Ilegal!!
            } 
        }
        AcaoEstado[] acoes_estados = new AcaoEstado[lista.size()];
        Iterator iter=lista.iterator();
        for (int i=0; iter.hasNext(); i++) {
            acoes_estados[i]=(AcaoEstado)iter.next();
        }
        return acoes_estados;
    }
    
    /**
     * Determina o custo de se fazer o movimento
     * 
     */
    public double custoCaminho(Acao action) {
        return 1;
    }
    
    /**
      * Exemplo de heurística adimissível
     */ 
    public static int distance(int[][] a, int[][] b) {
        int dist=0;
        for (int r1=0; r1<a.length; r1++) {
            for (int c1=0; c1<a[r1].length; c1++) {
                if (a[r1][c1]!=b[r1][c1])
                    dist++;
            }
        }
        return dist;
    }
    
    /*
     * Heurística de manhattan entre dois estados
     */ 
    public static int manhattanDistance(int[][] a, int[][] b) {
    	int i, x, y, deveriaSer,
			dist = 0,
			larguraTabuleiro = a.length,
			tamTabuleiro = (int) Math.pow(larguraTabuleiro, 2),
			aSquashed[] = new int[tamTabuleiro],
			bSquashed[] = new int[tamTabuleiro];
		
		// Compara 2 arrays de peças
		for ( i = 0; i < tamTabuleiro; i++ ) {
			x = (int) Math.floor(i / larguraTabuleiro);
			y = i % larguraTabuleiro;
			aSquashed[i] = a[x][y];
			/* Permite verificar posição real das peças sem ter que iterar o array novamente	 * having to loop through the whole array again */
			bSquashed[b[x][y]] = i;
		}
		
		// Acha peças fora do lugar
		for ( i = 0; i < tamTabuleiro; i++ ) {
			deveriaSer = bSquashed[aSquashed[i]];
			if (i != deveriaSer) {
				// Peça fora do lugar. Soma das distancias horizontal e vertical da posição correta da peça
				dist += Math.abs((i / larguraTabuleiro) - (deveriaSer / larguraTabuleiro)) +
						Math.abs((i % larguraTabuleiro) - (deveriaSer % larguraTabuleiro));
			}
		}
		return dist;
    }

    /**
     * Compara se o estado fornecido é igual ao estado atual
     */
    public boolean equals(Object obj) {
        if (obj.getClass().equals(this.getClass())) {
            NPuzzleEstado state=(NPuzzleEstado)obj;
            for (int r=0; r<pecas.length; r++) {    
                for (int c=0; c<pecas[r].length; c++) {
                    if (state.pecas[r][c]!=pecas[r][c])
                        return false;
                }
            }
            return true;
        }
        return false;
    }
    
    /**
     * Imprime a configuração do tabuleiro
     */
    public String toString() {
        DecimalFormat nf=new DecimalFormat("00");
        StringBuffer sb=new StringBuffer();
        for (int r=0; r<pecas.length; r++) {
            for (int c=0; c<pecas[r].length; c++) {
                if (pecas[r][c] != 0)
                sb.append("["+nf.format(pecas[r][c])+"]");
                else
                sb.append("[  ]");    
            }
            sb.append("\n");
        }
        return sb.toString();
    }

}
